from BuildTree import *


class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        self.ans = 0

        def dfs(node: TreeNode) -> list[int]:
            # 以node开始的节点值有多少类型
            if not node: return []
            l = dfs(node.left)
            r = dfs(node.right)
            ans = [node.val + val for val in l + r] + [node.val]
            self.ans += sum(1 for i in ans if i == targetSum)
            return ans

        dfs(root)
        return self.ans


if __name__ == '__main__':
    s = Solution()
    root = build_tree_from_level_order([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1])
    r = s.pathSum(root, 22)
    print(r)
